using System;
using System.Linq;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0332. 重新安排行程")]
    public class No0332_FindItinerary : AbsBaseTestItem
    {
        /*
        给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
        提示：
            如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
            所有的机场都用三个大写字母表示（机场代码）。
            假定所有机票至少存在一种合理的行程。
            所有的机票必须都用一次 且 只能用一次。
        */

        public override void OnTest()
        {
            Assert.TestExe(FindItinerary,
                new List<IList<string>>()
                {
                    new string[] {"MUC", "LHR"},
                    new string[] {"JFK", "MUC"},
                    new string[] {"SFO", "SJC"},
                    new string[] {"LHR", "SFO"},
                },
                new string[] { "JFK", "MUC", "LHR", "SFO", "SJC" });

            Assert.TestExe(FindItinerary,
                new List<IList<string>>()
                {
                    new string[] {"JFK","SFO"},
                    new string[] {"JFK","ATL"},
                    new string[] {"SFO","ATL"},
                    new string[] {"ATL","JFK"},
                    new string[] {"ATL","SFO"},
                },
                new string[] { "JFK", "ATL", "JFK", "SFO", "ATL", "SFO" });
        }

        public IList<string> FindItinerary(IList<IList<string>> tickets)
        {
            var dic = new Dictionary<string, List<string>>();
            foreach (var ticket in tickets)
            {
                string src = ticket[0], dst = ticket[1];
                if (!dic.ContainsKey(src))
                {
                    dic[src] = new List<string>();
                }
                dic[src].Add(dst);
            }
            foreach (var key in dic.Keys)
            {
                dic[key].Sort();
            }
            var ans = new List<string>();
            void dfs(string curr)
            {
                while (dic.ContainsKey(curr) && dic[curr].Count > 0)
                {
                    string tmp = dic[curr][0];
                    dic[curr].RemoveAt(0);
                    dfs(tmp);
                }
                ans.Add(curr);
            }
            dfs("JFK");
            ans.Reverse();
            return ans;
        }
    }
}
